/**
 * FileName: TestCycleDetectionForAdjacencyLists.c
 * --------------------------------------------------------------------------------------------------------------------
 * 邻接列表实现的图的环检测骨架代码
 * - 适合稀疏图
 *
 */
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//顶点相关
typedef struct node* link;
struct node {
    int v;
    link next;
};

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    link* adj;
};

#define dfsR3 search

static int* pre;
static int* st;
static int cnt;
int depth = 0; // 全局变量表示递归深度，用来控制缩进量


//辅助函数声明
void HELPinit(int);
void HELPcleanUp();
link NEW(int, link);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void dfsR(Graph, Edge);
void dfsR2(Graph, Edge);
void dfsR3(Graph, Edge);
void printIndent();
void show(char*, Edge);
int dfsRHasCycle(Graph, Edge);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
int GRAPHhasCycle(Graph);

//辅助函数实现
void HELPinit(int maxV) {
    //全局变量初始化
    cnt = 0;
    int v;
    pre = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        pre[v] = -1;
    }
    depth = 0;
    st = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        st[v] = -1;
    }

}

void HELPcleanUp() {
    free(pre);
    free(st);
}

link NEW(int v, link next) {
    link x = (link) malloc(sizeof(*x));
    x->v = v;
    x->next = next;
    return x;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    printf("%d vertices, %d edges\n", G->V, G->E);
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        printf("%2d:", v);
        for (t = G->adj[v]; t != NULL; t = t->next) {
            printf(" %2d", t->v);
        }
        printf("\n");
    }
}

/**
 * Program 18.2 Depth-first search (adjacency-lists)
 * ---------------------------------------------------------------------------------------------------------------------
 * This implementation of `dfsR` is DFS for graphs represented with adjacency lists.
 *
 * The algorithm is the same as for the adjacency-matrix representation (Program 18.1):
 * to visit a vertex, we
 * - mark it and
 * - then scan through its incident edges, making a recursive call whenever we encounter an edge to an unmarked vertex.
 * ---------------------------------------------------------------------------------------------------------------------
 * dfs递归版
 * @param G
 * @param e
 */
void dfsR(Graph G, Edge e) {
    link t;
    int w = e.w;
    pre[w] = cnt++;
    st[e.w] = e.v;
    Edge x;
    for (t = G->adj[w]; t != NULL; t = t->next) {
        x = EDGE(w, t->v);
        if (pre[t->v] == -1) {
            // w指向t->v的边 tree link
            dfsR(G, x);
        }else if (st[w] == t->v) {
            // w指向t->v的边 parent link
        }else if (pre[w] > pre[t->v]) {
            // w指向t->v的边 back link
        }else if (pre[w] < pre[t->v]) {
            // w指向t->v的边 down link
        }
    }

}

void dfsR2(Graph G, Edge e) {
    link t;
    int w = e.w;
    show("", e);
    depth++;
    pre[w] = cnt++;
    st[e.w] = e.v;
    Edge x;
    for (t = G->adj[w]; t != NULL; t = t->next) {
        x = EDGE(w, t->v);
        if (pre[t->v] == -1) {
            // w指向t->v的边 tree link
            dfsR2(G, x);
        }else if (st[w] == t->v) {
            // w指向t->v的边 parent link
            show("", x);
        }else if (pre[w] > pre[t->v]) {
            // w指向t->v的边 back link
            show("", x);
        }else if (pre[w] < pre[t->v]) {
            // w指向t->v的边 down link
            show("", x);
        }
    }
    depth--;

}

void dfsR3(Graph G, Edge e) {
    link t;
    int w = e.w;
    Edge x;

    show("tree", e);
    depth++;
    pre[w] = cnt++;
    st[w] = e.v;
    for (t = G->adj[w]; t != NULL; t = t->next) {
        x = EDGE(w, t->v);
        if (pre[t->v] == -1) {
            // w指向t->v的边 tree link
            dfsR3(G, x);
        }else if (st[w] == t->v) {
            // w指向t->v的边 parent link
            show("parent", x);
        }else if (pre[w] > pre[t->v]) {
            // w指向t->v的边 back link
            show("back", x);
        }else if (pre[w] < pre[t->v]) {
            // w指向t->v的边 down link
            show("down", x);
        }
    }
    depth--;
}

void printIndent() {
    int i;
    for (i = 0; i < depth; i++) {
        printf("  "); // 每层缩进2个空格
    }
}

void show(char* key, Edge e) {
    printIndent();
    printf("%d-%d %s\n", e.v, e.w, key);
}

int dfsRHasCycle(Graph G, Edge e) {
    link t;
    int w = e.w;
    pre[w] = cnt++;
    st[w] = e.v; //记录父节点
    for (t = G->adj[w]; t != NULL; t = t->next) {
        if (w == t->v) {
            //检测自环
            return 1;
        }
        if (pre[t->v] == -1) {
            //tree link: one of tree edge
            if (dfsRHasCycle(G, EDGE(w, t->v))) {
                return 1;
            }
        }else if (st[w] != t->v) {
            //back edge
            return 1;
        }
    }
    return 0;
}

//图操作函数实现
Graph GRAPHinit(int V) {
    int v;
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = (link*) malloc(V * sizeof(link));
    for (v = 0; v < V; v++) {
        G->adj[v] = NULL;
    }
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    G->adj[v] = NEW(w, G->adj[v]);
    G->adj[w] = NEW(v, G->adj[w]);
    G->E++;
}

void GRAPHremoveE(Graph G, Edge e) {
    link x1, x2;
    link t1, t2;
    int v = e.v;
    int w = e.w;

    //从v的邻接列表里找到w，删除该节点
    t1 = G->adj[v];
    while (t1 != NULL) {
        if (t1->v == w) {
            break;
        }
        x1 = t1;
        t1 = t1->next;
    }
    if (t1 == NULL) {
        return;
    }
    if (x1 == NULL) {
        //说明w是首节点
        G->adj[v] = t1->next;
    }else {
        x1->next = t1->next;
    }
    //从w的邻接列表出发找到v，删除该节点
    t2 = G->adj[w];
    while (t2 != NULL) {
        if (t2->v == v) {
            break;
        }
        x2 = t2;
        t2 = t2->next;
    }
    if (t2 == NULL) {
        return;
    }
    if (x2 == NULL) {
        //说明v是首节点
        G->adj[w] = t2->next;
    }else {
        x2->next = t2->next;
    }

    free(t1);
    free(t2);

    G->E--;
}
int GRAPHedges(Edge a[], Graph G) {
    int E = 0;
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            if (v < t->v) {
                a[E++] = EDGE(v, t->v);
            }
        }
    }

    return E;
}
Graph GRAPHcopy(Graph G) {
    Graph copy = GRAPHinit(G->V);
    int v;
    link t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            if (v < t->v) {
                GRAPHinsertE(copy, EDGE(v, t->v));
            }
        }
    }

    return copy;

}
void GRAPHdestroy(Graph G) {
    int v;
    for (v = 0; v < G->V; v++) {
        link t = G->adj[v];
        while (t != NULL) {
            link next = t->next;
            free(t);
            t = next;
        }
    }
    free(G->adj);
    free(G);
}

int GRAPHhasCycle(Graph G) {
    int v;
    HELPinit(G->V);
    for (v = 0; v < G->V; v++) {
        if (pre[v] == -1) {
            if (dfsRHasCycle(G, EDGE(v,v))) {
                return 1;
            }
        }
    }
    return 0;
}

//测试函数声明
void test_one_cycle();
void test_cycles();


int main(int argc, char *argv[]) {
    test_one_cycle();
    test_cycles();
    return 0;
}

//测试函数实现
void test_one_cycle() {
    int V = 8;
    Graph G = GRAPHinit(V);
    HELPinit(G->V);

    GRAPHinsertE(G, EDGE(0, 2));
    GRAPHinsertE(G, EDGE(0, 5));
    GRAPHinsertE(G, EDGE(0, 7));
    GRAPHinsertE(G, EDGE(1, 7));
    GRAPHinsertE(G, EDGE(2, 6));
    GRAPHinsertE(G, EDGE(3, 4));
    GRAPHinsertE(G, EDGE(3, 5));
    GRAPHinsertE(G, EDGE(4, 5));
    GRAPHinsertE(G, EDGE(4, 6));
    GRAPHinsertE(G, EDGE(4, 7));

    // GRAPHshow(G);
    int hasCycle = GRAPHhasCycle(G);
    if (hasCycle) {
        printf("Graph has cycle\n");
    }else {
        printf("Graph has not cycle\n");
    }

    GRAPHdestroy(G);
    HELPcleanUp();
}

void test_cycles() {
    int V = 13;
    Graph G = GRAPHinit(V);
    HELPinit(G->V);

    GRAPHinsertE(G, EDGE(0, 1));
    GRAPHinsertE(G, EDGE(0, 2));
    GRAPHinsertE(G, EDGE(0, 5));
    GRAPHinsertE(G, EDGE(0, 6));
    GRAPHinsertE(G, EDGE(3, 4));
    GRAPHinsertE(G, EDGE(3, 5));
    GRAPHinsertE(G, EDGE(4, 5));
    GRAPHinsertE(G, EDGE(4, 6));
    GRAPHinsertE(G, EDGE(7, 8));
    GRAPHinsertE(G, EDGE(9, 10));
    GRAPHinsertE(G, EDGE(9, 11));
    GRAPHinsertE(G, EDGE(9, 12));
    GRAPHinsertE(G, EDGE(11, 12));

    int hasCycle = GRAPHhasCycle(G);
    if (hasCycle) {
        printf("Graph has cycle\n");
    }else {
        printf("Graph has not cycle\n");
    }

    GRAPHdestroy(G);
    HELPcleanUp();


}